package com.tgy.algorithm.base._并行计算;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class UninFindNode<V> {
    V value;
    public UninFindNode(V value) {
        this.value = value;
    }
}

class UninFind<V> {
    private Map<V,UninFindNode<V>> nodes;
    private Map<UninFindNode<V>,UninFindNode<V>> parents;
    private Map<UninFindNode<V>,Integer> counts;

    public UninFind() {
        nodes = new HashMap<>();
        parents = new HashMap<>();
        counts = new HashMap<>();
    }

    public void addNode(V value) {
        if (nodes.containsKey(value)) {
            return;
        }
        UninFindNode uninFindNode = new UninFindNode(value);
        nodes.put(value,uninFindNode);
        parents.put(uninFindNode,uninFindNode);
        counts.put(uninFindNode,1);
    }

    public boolean isSame(V one,V two) {

        if (!(nodes.containsKey(one) && nodes.containsKey(two))) {
            return false;
        }

        return findParent(nodes.get(one)) == findParent(nodes.get(two));
    }

    public void unin(V one, V two) {
        if (!(nodes.containsKey(one) && nodes.containsKey(two))) {
            return;
        }

        UninFindNode<V> oneNode = nodes.get(one);
        UninFindNode<V> twoNode = nodes.get(two);
        UninFindNode<V> parentOne = findParent(oneNode);
        UninFindNode<V> parentTwo = findParent(twoNode);

        if (parentOne == parentTwo) {
            return;
        }

        if (counts.get(parentOne) >= counts.get(parentTwo)) {
            parents.put(twoNode,parentOne);
            counts.put(parentOne,counts.get(parentOne)+counts.get(parentTwo));
            counts.remove(parentTwo);
        }else {
            parents.put(oneNode,parentTwo);
            counts.put(parentTwo,counts.get(parentOne)+counts.get(parentTwo));
            counts.remove(parentOne);
        }
    }

    public int collectCount() {
        return counts.values().size();
    }

    private UninFindNode<V> findParent(UninFindNode<V> node) {

        List<UninFindNode<V>> nodes = new ArrayList<>();
        while (node != parents.get(node)) {
            nodes.add(node);
            node = parents.get(node);
        }

        // 压扁node
        for (UninFindNode<V> nd : nodes) {
            parents.put(nd,node);
        }

        return node;
    }

}

public class _并查集 {



    public static void main(String[] args) {

        String[] strs = new String[]{"111","22","333","444"};
        UninFind<String> uninFind = new UninFind<>();
        for (String str : strs) {
            uninFind.addNode(str);
        }

        uninFind.unin("111","333");
        uninFind.unin("22","444");

        int collectCount = uninFind.collectCount();
        System.out.println(collectCount);
    }
}
